
/****************************************************************************/
/*Copyright (c) 2011, Florent DEVILLE.                                      */
/*All rights reserved.                                                      */
/*                                                                          */
/*Redistribution and use in source and binary forms, with or without        */
/*modification, are permitted provided that the following conditions        */
/*are met:                                                                  */
/*                                                                          */
/* - Redistributions of source code must retain the above copyright         */
/*notice, this list of conditions and the following disclaimer.             */
/* - Redistributions in binary form must reproduce the above                */
/*copyright notice, this list of conditions and the following               */
/*disclaimer in the documentation and/or other materials provided           */
/*with the distribution.                                                    */
/* - The names of its contributors cannot be used to endorse or promote     */
/*products derived from this software without specific prior written        */
/*permission.                                                               */
/* - The source code cannot be used for commercial purposes without         */ 
/*its contributors' permission.                                             */
/*                                                                          */
/*THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS       */
/*"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT         */
/*LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS         */
/*FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE            */
/*COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,       */
/*INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,      */
/*BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;          */
/*LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER          */
/*CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT        */
/*LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN         */
/*ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE           */
/*POSSIBILITY OF SUCH DAMAGE.                                               */
/****************************************************************************/

#include "RTCSGNode.h"
#include "RTIPrimitive.h"

namespace RT
{
	/*Default constructor*/
	RTCSGNode::RTCSGNode(): m_RTPrimitive(0), m_boolType(eBoolUnion)
	{
		m_children[0] = 0;
		m_children[1] = 0;
	}

	/*Constructor*/
	RTCSGNode::RTCSGNode(RTIPrimitive* p, eBoolType b, RTCSGNode* child1, RTCSGNode* child2):m_RTPrimitive(p), m_boolType(b)
	{
			m_children[0] = child1;
			m_children[1] = child2;				
	}

	/*Destructor*/
	RTCSGNode::~RTCSGNode()
	{
		if(m_RTPrimitive != 0)
			delete m_RTPrimitive;

		if(m_children[0] != 0)
			delete m_children[0];

		if(m_children[1] != 0)
			delete m_children[1];
	}

	/*Check if there is an intersection between this node and a ray.*/
	bool RTCSGNode::checkIntersection(const RTRay& r, F32& dist, RTVector3f& normal)const
	{
		dist = 0;

		//we are already in the local coordinates of the CSG (but not of the RTPrimitives)

		//leaf
		bool intersection;
		if(m_children[0] == 0 && m_children[1] == 0)
		{
			//check intersection
			intersection = m_RTPrimitive->intersect(r, dist, false);
			if(!intersection)
				return false;

			//if intersection, compute normal
			m_RTPrimitive->computeNormal(r, dist, normal);
			return true;
		}

		//branch
		switch(m_boolType)
		{
			case eBoolUnion:
				return checkIntersectionUnion(r, dist, normal);
			
			case eBoolIntersection:
				return checkIntersectionInter(r, dist, normal);

			case eBoolDifference:
				return checkIntersectionDiff(r, dist, normal);

			default:
				return false;
		}


	}

	/*Check if a given point is inside the node*/
	bool RTCSGNode::isInside(const RTVector3f& p)const
	{
		//leaf
		if(m_children[0] == 0 && m_children[1] == 0)
			return m_RTPrimitive->isInside(p);

		//branch
		switch(m_boolType)
		{
			case eBoolUnion:
				if(m_children[0]->isInside(p) || m_children[1]->isInside(p))
					return true;

				return false;
				break;

			case eBoolIntersection:
				if(m_children[0]->isInside(p) && m_children[1]->isInside(p))
					return true;

				return false;
				break;

			case eBoolDifference:
				if(m_children[0]->isInside(p) && !m_children[1]->isInside(p))
					return true;

				return false;
				break;

			default:
				return false;
		}
	}

	/*Apply an identity view matrix to this node and to it's children recursively.*/
	void RTCSGNode::applyNullViewMatrix()
	{
		if(m_RTPrimitive != 0)
		{
			RTMatrix44 view;
			view.identity();
			m_RTPrimitive->applyViewMatrix(view);
		}

		if(m_children[0] != 0)
			m_children[0]->applyNullViewMatrix();

		if(m_children[1] != 0)
			m_children[1]->applyNullViewMatrix();
	}

	/*Check if there is an intersection between the ray and the two children using a union boolean operator*/
	bool RTCSGNode::checkIntersectionUnion(const RTRay& r, F32& dist, RTVector3f& normal)const
	{
		F32 dist1, dist2;
		RTVector3f normal1, normal2;

		bool I32er1 = m_children[0]->checkIntersection(r, dist1, normal1);
		bool I32er2 = m_children[1]->checkIntersection(r, dist2, normal2);

		//no intersection
		if(!I32er1 && !I32er2)
			return false;
		//two intersections
		else if(I32er1 && I32er2)
		{
			//compute the two intersections poI32s
			RTVector3f p1 = r.getOrigin() + r.getDirection() * dist1;
			RTVector3f p2 = r.getOrigin() + r.getDirection() * dist2;

			//if the two poI32s are outside surfaces
			bool p2Inside = m_children[0]->isInside(p2);
			bool p1Inside = m_children[1]->isInside(p1);

			if(dist1 == dist2)
			{
				dist = dist1;
				normal = normal1;
				return true;
			}
			if(!p2Inside && !p1Inside)
			{
				//take the closest
				if(dist1 < dist2)
				{
					dist = dist1;
					normal = normal1;
					return true;
				}
				else
				{
					dist = dist2;
					normal = normal2;
					return true;
				}
			}
			//now at least one inside
			else if(p2Inside && !p1Inside)//if p1 is outside
			{
				dist = dist1;
				normal = normal1;
				return true;
			}
			else if(p1Inside && !p2Inside) //p2 outside
			{
				dist = dist2;
				normal = normal2;
				return true;
			}
			// both inside
			else 
			{
				//get the farthest poI32
				F32 longest = dist1 < dist2? dist1 : dist2;
				longest += 0.01f;

				//calculate the new origin
				RTVector3f newOrigin = r.getOrigin() + r.getDirection() * longest;

				//create new ray
				RTRay newR = r;
				newR.setOrigin(newOrigin);

				//recursive call
				F32 newDist = 0;
				bool res = checkIntersectionUnion(newR, newDist, normal);

				//update the dist
				if(res)
					dist += (newOrigin - r.getOrigin()).norme() + newDist;

				return res;
			}
		}
		else if (I32er1)//one intersection
		{
			dist = dist1;
			normal = normal1;
			return true;
		}
		else
		{
			dist = dist2;
			normal = normal2;
			return true;
		}

	}

	/*Check if there is an intersection between the ray and the two children using an intersection boolean operator*/
	bool RTCSGNode::checkIntersectionInter(const RTRay& r, F32& dist, RTVector3f& normal)const
	{
		F32 dist1, dist2;
		RTVector3f normal1, normal2;
		bool I32er1, I32er2;

		I32er1 = m_children[0]->checkIntersection(r, dist1, normal1);
		I32er2 = m_children[1]->checkIntersection(r, dist2, normal2);

		//no intersection
		if(!I32er1 || !I32er2)
		{
			return false;
		}
		else //two intersection
		{
			//get the two intersections poI32s
			RTVector3f p0 = r.getOrigin() + r.getDirection() * dist1;
			RTVector3f p1 = r.getOrigin() + r.getDirection() * dist2;

			if(dist1 == dist2)
			{
				dist = dist1;
				normal = normal1;
				return true;
			}
			//if p0 is inside children1 then p0 is the intersection poI32
			if(m_children[1]->isInside(p0))
			{
				dist = dist1;
				normal = normal1;
				return true;
			}
			else if(m_children[0]->isInside(p1))
			{
				dist = dist2;
				normal = normal2;
				return true;
			}
			else//recursive call
			{
				//get longest distance
				F32 longest = dist1 < dist2? dist2 : dist1;
				longest += 0.01f;

				//compute new origin poI32
				RTVector3f newOrigin = r.getOrigin() + r.getDirection() * longest;

				//compute new ray
				RTRay newRay = r;
				newRay.setOrigin(newOrigin);

				//compute intersection
				F32 newDist = 0;
				bool res = checkIntersectionInter(newRay, newDist, normal);

				//set the dist
				if(res)
					dist += (r.getOrigin() - newOrigin).norme() + newDist;

				return res;
			}
		}

		//only one intersection
		//return false;
	}

	/*Check if there is an intersection between the ray and the two children using a substract boolean operator*/
	bool RTCSGNode::checkIntersectionDiff(const RTRay& r, F32& dist, RTVector3f& normal)const
	{
		F32 dist0, dist1;
		RTVector3f normal0, normal1;

		//get the intersection
		bool I32er0 = m_children[0]->checkIntersection(r, dist0, normal0);
		bool I32er1 = m_children[1]->checkIntersection(r, dist1, normal1);

		//no intersection
		if(!I32er0 && !I32er1)
			return false;

		//two intersections
		else if(I32er0 && I32er1)
		{
			//calculate the intersection poI32
			RTVector3f p1 = r.getOrigin() + r.getDirection() * dist1;
			RTVector3f p0 = r.getOrigin() + r.getDirection() * dist0;
			if(dist1 == dist0)
			{
				dist = dist1;
				normal = normal1;
				return true;
			}
			if(dist1 < dist0)
			{
				bool p1Inside = m_children[0]->isInside(p1);
				bool p0Inside = m_children[1]->isInside(p0);
				if(p1Inside)
				{
					dist = dist1;
					normal = normal1;
					return true;
				}
				else if(!p1Inside && !p0Inside)
				{
					dist = dist0;
					normal = normal0;
					return true;
				}
				else
				{
					//get the furthest poI32
					F32 longest = 0.01f;
					if(p0Inside)
						longest += dist0;
					else 
						longest += dist1;

					//compute new origin
					RTVector3f newOrigin = r.getOrigin() + r.getDirection() * longest;
				
					//create new ray
					RTRay newRay = r;
					newRay.setOrigin(newOrigin);
				
					//recurisive call
					F32 newDist = 0;
					bool res = checkIntersectionDiff(newRay, newDist, normal);

					//update the distance
					if(res)
						dist = (newOrigin - r.getOrigin()).norme() + newDist;

					return res;
				}
			}
			else
			{
				//bool p1Inside = m_children[0]->isInside(p1);
				bool p0Inside = m_children[1]->isInside(p0);
				if(!p0Inside)
				{
					dist = dist0;
					normal = normal0;
					return true;
				}
				else
				{
					//get the furthest poI32
					F32 longest = dist0 + 0.01f;

					//compute new origin
					RTVector3f newOrigin = r.getOrigin() + r.getDirection() * longest;
				
					//create new ray
					RTRay newRay = r;
					newRay.setOrigin(newOrigin);
				
					//recurisive call
					F32 newDist = 0;
					bool res = checkIntersectionDiff(newRay, newDist, normal);

					//update the distance
					if(res)
						dist = (newOrigin - r.getOrigin()).norme() + newDist;

					return res;
				}
			}
		}
		else if(I32er0)
		{
			dist = dist0;
			normal = normal0;
			return true;
		}
		else//I32er1
		{
			//calculate the intersection poI32
			RTVector3f p1 = r.getOrigin() + r.getDirection() * dist1;

			if(m_children[0]->isInside(p1))
			{
				dist = dist1;
				normal = normal1;
				return true;
			}
			else
				return false;
		}
		
		//something's wrong
		//return false;
	}

}